package heap;

import array.MyArray;


/**
 * 使用动态数组来实现最大堆
 * @param <E>
 */
public class MaxHeap<E extends Comparable<E>> {
    private MyArray<E> data;

    public MaxHeap(int capacity){
        data = new MyArray<E>(capacity);
    }

    public MaxHeap(){
        data = new MyArray<E>();
    }


    public int size(){
        return data.getSize()        ;
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回完全二叉树数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){

        if(index == 0){
            //0 索引没有父节点
        }
        return (index-1)/2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }


    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index*2 + 2;
    }

    // 向堆中添加元素
    public void add(E e){
        data.addLast(e);

        //需要维护堆的性质：需要 Sift Up（上浮）
        siftUp(data.getSize() - 1);

    }

    /**
     *
     * @param k：需要上浮的元素的下标，从
     */
    private void siftUp(int k){
        // k的父元素 与 k比较，父元素比k小的话，继续循环
        // k > 0：
        while ( k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            //位置交换
            data.swap(k,parent(k));

            k = parent(k);  //渐进条件
        }
    }

    //查看堆中最大元素
    public E findMax(){
        if(data.getSize() == 0){
            throw new IllegalArgumentException("堆中并无元素！");
        }
        return data.get(0);
    }

    //取出堆中最大元素
    public E extrackMax(){

        E ret = findMax();
        //交换 下标为0的元素 和 下标为 data.length -1 的元素,交换之后，堆中的最后一个元素就是最大的元素
        data.swap(0,data.getSize()-1);
        //将最大元素删除
        data.removeLast();
        //维护堆的性质，下沉
        siftDown(0);
        return ret;

    }

    /**
     * 下沉
     * step1：获取指定下标的节点
     * step2：比较 指定元素 的 左右两个子节点的值
     * step3：比较 指定节点 与 左右两个子节点中 更大 的节点
     * @param k
     */
    private void siftDown(int k){
        while (leftChild(k) < data.getSize()){  //data没有左孩子，表示是叶子节点
            int j = leftChild(k);
            //j + 1 < data.getSize(): 存在右孩子
            //data.get(j+1).compareTo(data.get(j)) > 0：右孩子的值大于左孩子的值
            if( j + 1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                j = rightChild(k);
                //此时 data[j] 是 leftChild 和 rightChild 中最大值
            }

            if(data.get(k).compareTo(data.get(j)) > 0){
                //此时k节点的值比左右孩子的值都大，就不需要下沉了
                break;
            }

            data.swap(k,j);
            k = j;  //渐进条件
        }
    }

    /**
     * 取出堆中最大的元素，并且替换成最新的元素e
     * step1：取出最大元素
     * step2：将 0 位置的元素放置成最新元素
     * step3：使用下沉方法来维护堆的结构
     * @param e
     * @return
     */
    public E replace(E e){
        E ret = findMax();
        //替换掉最大元素
        data.set(0,e);
        siftDown(0);    //元素下沉
        return ret;
    }


    //将任意数组整理成堆的形状
    public void heapify(E[] arr){
        data = new MyArray<E>(arr);
        //最后一个叶子的父亲节点下标
        int parentIndex = parent(arr.length - 1);
        for (int i = parentIndex ; i > 0; i--) {
            siftDown(i);
        }

    }







}
